/*
题目描述：链表中环的入口结点
方法：双指针
1. 判断是否有环，双指针不同速度走，能相遇，有环；快指针到达null， 无环
2. 快指针先走 n 步， 然后两个指针同速度走，相遇的结点即为入口结点
 */
public class E23 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        ListNode temp = head.next.next;
        head.next.next.next.next.next.next = temp;

        ListNode res = EntryNodeOfLoop(head);

        if(res != null)
            System.out.println(res.value);
    }

    public static ListNode EntryNodeOfLoop(ListNode pHead){
        ListNode meetingNode = MeetingNode(pHead);
        if(meetingNode == null){
            return null;
        }
        //找到环的长度
        int cycleLen = 1;
        ListNode temp = meetingNode;
        while(temp.next != meetingNode){
            temp = temp.next;
            cycleLen ++;
        }

        ListNode pAhead = pHead, pBehind = pHead;
        //pHead先走
        for(int i = 0; i < cycleLen; i++){
            pAhead = pAhead.next;
        }
        while(pAhead != pBehind){
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }
        return pAhead;
    }

    public static ListNode MeetingNode(ListNode pHead){
        if(pHead == null){
            return null;
        }
        ListNode pSlow = pHead.next;
        if(pSlow == null){
            return null;
        }
        ListNode pFast = pSlow.next;
        while(pSlow != null && pFast != null){
            if(pSlow == pFast){
                return pSlow;
            }
            pSlow = pSlow.next;

            pFast = pFast.next;
            if(pFast != null){
                pFast = pFast.next;
            }
        }
        return null;
    }
}
